We consider the complexity of finding a correlated equilibrium of an$n$-player game in a model that allows the algorithm to make queries onplayers' payoffs at pure strategy profiles. Randomized regret-based dynamicsare known to yield an approximate correlated equilibrium efficiently, namely,in time that is polynomial in the number of players $n$. Here we show that bothrandomization and approximation are necessary: no efficient deterministicalgorithm can reach even an approximate correlated equilibrium, and noefficient randomized algorithm can reach an exact correlated equilibrium. Theresults are obtained by bounding from below the number of payoff queries thatare needed.
展开▼
机译：我们考虑在模型中寻找一个n $ n玩家游戏的相关均衡的复杂性，该模型允许算法在纯策略配置文件中根据玩家的收益进行查询。已知基于随机后悔的动力学有效地产生近似的相关平衡，即，时间是玩家数$ n $的多项式。在这里，我们证明了随机化和逼近都是必要的：没有有效的确定性算法甚至不能达到近似相关均衡，没有效率的随机算法也不能达到精确相关均衡。通过从下面限制所需的支付查询的数量来获得结果。
展开▼
